package Data_Structure.Stack;

import java.util.Arrays;

/**
 * @className: MyStack
 * @author: 芃
 * @description: 模拟实现栈-数组模拟
 * @date: 2023/8/21 16:03
 */
//采用单链表能否实现栈？
//此处用数组模拟实现的栈，插入和删除的时间复杂度都是O（1）
//要想实现时间复杂度为O（1）的栈，头插还是尾插？
//答案是头插，入栈的时候，直接插到头节点的前面即可，出栈的时候也直接出头节点即可。
//使用链表模拟栈可以减少扩容带来的时间开销，但是需要维护头节点信息
public class MyStack {
    private int[] array = new int[10];
    private int usedSize = 0;

    //构造方法
    public MyStack() {
    }

    //判断空
    public boolean isEmpty(){
        return usedSize == 0;
    }

    //判断满
    private boolean isFull(){
        return this.usedSize == this.array.length;
    }

    //扩容->2倍扩
    public void grow(){
        this.array = Arrays.copyOf(this.array,2*this.array.length);
    }

    //放元素
    public void push(int val){
        if (isFull()){
            //扩容
            grow();
        }
        this.array[usedSize] = val;
        usedSize++;
    }

    //弹出元素
    public int pop(){
        if(isEmpty()){
            throw new RuntimeException("栈为空");
        }
        int val = this.array[usedSize-1];
        usedSize--;
        return val;
    }

    //查看栈顶元素
    public int peek(){
        if (isEmpty()){
            throw new RuntimeException("栈为空");
        }
        return this.array[usedSize-1];
    }
}
